package com.dycong.common.leetcode;

import com.dycong.common.leetcode.ds.tree.TreeNode;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * @author dycong
 * @date 2019/9/24 8:52
 * 给定两个二叉树，编写一个函数来检验它们是否相同。
 * <p>
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 */
public class SameTree_100 {

    /*
    大多数的二叉树题目都是用递归可以解的。
所以当拿到二叉树的题目的时候，我们首先就是看看能拆解成哪些子问题。
这个问题的子问题很简单，就是左子树，右子树都相等的二叉树是相同的二叉树。
     */

    @Test
    public void test() {

    }

    /*
    分解为 递归判断左右子树是否相同
    DFS
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (Objects.isNull(p) && Objects.isNull(q)) {
            return true;
        } else if (Objects.isNull(p) || Objects.isNull(q)) {
            return false;
        }

        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public boolean isSameTree_bfs(TreeNode p, TreeNode q) {
        if (Objects.isNull(p) && Objects.isNull(q)) {
            return true;
        } else if (Objects.isNull(p) || Objects.isNull(q)) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(p);
        queue.add(q);

        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            // 有一个为null
            if (right == null) {
                return false;
            }
            // 不相等.
            if (left.val != right.val) {
                return false;
            }
            // 左子树入队
            queue.add(left.left);
            queue.add(right.left);
            // 右子树入队
            queue.add(left.right);
            queue.add(right.right);
        }
        return true;
    }


}
